package com.xcc.dataStructures.demo14_algapplication;

import java.util.Arrays;

/**
 * KMP算法
 */
public class Demo04_KMP {

    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        int[] next = kmpNext(str2);
        System.out.println(kmp(str1, str2, next));
        System.out.println(kmpMatch(str1, str2));
    }

    /**
     * kmp算法
     *
     * @param src  原始的数据
     * @param dest 需要匹配的数据
     * @param next next数组
     * @return 返回下标，如果不满足返回-1
     */
    public static int kmp(String src, String dest, int[] next) {
        int len = src.length();
        for (int i = 0, j = 0; i < len; i++) {
            while (j > 0 && src.charAt(i) != dest.charAt(j)) {
                j = next[j - 1];
            }
            if (src.charAt(i) == dest.charAt(j)) {
                j++;
            }
            if (j == dest.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }

    /**
     * 获取需要被匹配字符串的next数组
     *
     * @param dest 目标字符串
     */
    public static int[] kmpNext(String dest) {
        //创建一个 next 数组保存部分匹配值
        int[] next = new int[dest.length()];
        next[0] = 0;//如果字符串是长度为 1 部分匹配值就是 0
        for (int i = 1, j = 0; i < dest.length(); i++) {
            //在ABCDABD中当匹配到ABCDAB时 此时i=6,j=2 此时回退到j=next[1-1]=next[0]
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j - 1];
            }
            //当 dest.charAt(i) == dest.charAt(j) 满足时，部分匹配值就是+1
            if (dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    /**
     * 对主串s和模式串t进行KMP模式匹配
     *
     * @param s 主串
     * @param t 模式串
     * @return 若匹配成功，返回t在s中的位置（第一个相同字符对应的位置），若匹配失败，返回-1
     */
    public static int kmpMatch(String s, String t) {
        char[] s_arr = s.toCharArray();
        char[] t_arr = t.toCharArray();
        int[] next = getNextArray(t_arr);
        int i = 0, j = 0;
        while (i < s_arr.length && j < t_arr.length) {
            if (j == -1 || s_arr[i] == t_arr[j]) {
                i++;
                j++;
            } else
                j = next[j];
        }
        if (j == t_arr.length)
            return i - j;
        else
            return -1;
    }

    /**
     * 求出一个字符数组的next数组
     *
     * @param p 字符数组
     * @return next数组
     */
    public static int[] getNextArray(char[] p) {
        int[] next = new int[p.length];
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < p.length - 1) {
            //p[k]表示前缀 p[j]表示后缀
            if (k == -1 || p[j] == p[k]) {
//                k++;
//                j++;
                next[++j] = ++k;
            } else {
                k = next[k];
            }
        }
        return next;
    }

}
